package 高效制胜._01;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/7 9:13
 * 两数之和 II - 输入有序数组
 * 算法：二分查找  双指针
 * 二分查找也算是双指针吧，今天才发现
 * 碰到有序的，可以优先考虑二分查找
 * 定义两个前后指针
 * 将指针所指的数相加，跟 target 比一下
 * 如果比 target 大，那么后指针往前移
 * 否则前指针往后移
 */
public class _167 {
    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        System.out.println(new _167().twoSum(numbers, target));
    }

    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return new int[]{l + 1, r + 1};
            if (sum > target) --r;
            else ++l;
        }
        return new int[0];
    }

}
